#include "../tools.h"

// ！！！需要元素有序

// 无重复数查找
int bsearch(const vector<int>& nums, int target){
    int left = 0, right = nums.size() - 1; //
    while(left <= right){ // left > right 时结束
        int mid = left + (right - left) / 2;
        if(nums[mid] == target) return mid;
        else if(target < nums[mid]) right = mid - 1;
        else if(nums[mid] < target) left = mid + 1;
    }
    return -1;
}

// 有重复，左边界查找
int upper_bsearch(const vector<int>& nums, int target){
    int left = 0, right = nums.size(); //
    while(left < right){ // left == right 时结束
        int mid = left + (right - left) / 2;
        if(nums[mid] == target) left = mid + 1;
        else if(target < nums[mid]) right = mid;
        else if(nums[mid] < target) left = mid + 1;
    }
    return left;        // [0, nums.size()] -> 返回的索引可能越界
}

// 有重复，右边界查找
int lower_bsearch(const vector<int>& nums, int target){
    int left = 0, right = nums.size();
    while(left < right){
        int mid = left + (right - left) / 2;
        if(target == nums[mid]) right = mid;
        else if(target < nums[mid]) right = mid;
        else if(nums[mid] < target) left = mid + 1;
    }
    return left;        // [0, nums.size()] -> 返回的索引可能越界
}


int main(int argc, char const *argv[])
{
    vector<int> nums = {-1,0,3,3,5,9,9,9,12};

    cout << bsearch(nums, 3) << endl;

    cout << upper_bsearch(nums, 3) << endl;
    cout << upper_bsearch(nums, 4) << endl;
    cout << upper_bsearch(nums, 14) << endl;
    cout << upper_bsearch(nums, -2) << endl;
    
    cout << endl;

    cout << lower_bsearch(nums, 3) << endl;
    cout << lower_bsearch(nums, 4) << endl;
    cout << lower_bsearch(nums, 14) << endl;
    cout << lower_bsearch(nums, -2) << endl;

    return 0;
}
